/*
 * KnuthMorrisPratt.cpp
 *
 *  Created on: 30-07-2013
 *      Author: Krzychu
 */

#include "KnuthMorrisPratt.h"

#include "Config.h"

#include <vector>

using namespace std;

KnuthMorrisPratt::KnuthMorrisPratt()
{

}

KnuthMorrisPratt::~KnuthMorrisPratt()
{

}

std::string KnuthMorrisPratt::getName()
{
	return "Knuth-Morris-Pratt";
}

int* KnuthMorrisPratt::preKmp(std::string prefix)
{
	int prefixLength = prefix.length();

	int* result = new int[prefixLength + 1];

	int i, j;

	i = 0;
	j = result[0] = -1;
	while (i < prefixLength)
	{
		while (j > -1 && prefix[i] != prefix[j])
		{
			j = result[j];
		}
		i++;
		j++;
		if (prefix[i] == prefix[j])
		{
			result[i] = result[j];
		}
		else
		{
			result[i] = j;
		}
	}

	return result;
}

searchResult KnuthMorrisPratt::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textLength = text.length();
	int patternLength = pattern.length();

	int i, j;

	/* Preprocessing */
	int* kmpNext = preKmp(pattern);

	/* Searching */
	i = j = 0;
	while (j < textLength)
	{
		result.iterationsTaken++;

		while (i > -1 && pattern[i] != text[j])
		{
			i = kmpNext[i];
		}
		i++;
		j++;
		if (i >= patternLength)
		{
			result.positionsFound.push_back(j - i);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
			i = kmpNext[i];
		}
	}

	return result;
}
